/**
 * 面试题 02.04. 分割链表
 * https://leetcode-cn.com/problems/partition-list-lcci/
 */
public class Solutions_mianshi_02_04 {
    public static void main(String[] args) {
        int[] arr = {3, 5, 8, 5, 10, 2, 1};
        int x = 5;  // output: {3, 1, 2, 10, 5, 5, 8}

        ListNode head = MyLinkedListUtils.ArrayToListNode(arr);
        ListNode result = partition(head, x);
        System.out.println(MyLinkedListUtils.ListNodeToString(result));
    }

    /**
     * 解题思路：将 head 中结点值小于 x 和大于等于 x 的结点，分别链接到 min 和 max 链表中
     * 最后拼接 min 和 max 链接，即保证了小于 x 的结点一定在大于等于 x 结点的前面
     */
    public static ListNode partition(ListNode head, int x) {
        ListNode min = new ListNode(-1);
        ListNode curMin = min;
        ListNode max = new ListNode(-1);
        ListNode curMax = max;

        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x) {
                curMin.next = cur;
                curMin = curMin.next;
            } else {
                curMax.next = cur;
                curMax = curMax.next;
            }
            cur = cur.next;
        }
        // min 链表的尾结点链接到 max 链表的头结点
        curMin.next = max.next;
        // max 链表的尾结点需要断链
        curMax.next = null;
        return min.next;
    }
}
